package com.melo;

import java.util.Arrays;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 普利姆算法: 解决村庄修路问题
 * @date 2025-05-19
 */
public class Prim {

    /**
     * 初始化村庄的全部链接矩阵: 所有顶点和所有顶点之间的连接路线
     *
     * @param graph      图对象: 村庄
     * @param vertexSize 图对应的顶点个数
     * @param vertexArr  图的各个顶点的值
     * @param weight     图的邻接矩阵
     */
    public static void initVillageGraph(PrimVillageGraph graph, int vertexSize, char[] vertexArr, int[][] weight) {
        graph.setVertexArr(vertexArr);
        int[][] weightArr = graph.getWeightArr();

        for (int i = 0; i < vertexSize; i++) {
            System.arraycopy(weight[i], 0, weightArr[i], 0, vertexSize);
        }
    }

    /**
     * 普利姆算法
     *
     * @param graph            图对象: 村庄
     * @param startVertexIndex 开始修路的顶点
     */
    public static void prim(PrimVillageGraph graph, int startVertexIndex) {
        int[][] weightArr = graph.getWeightArr();

        // 标记算法过程中被访问过的顶点: 1表示访问过, 0表示未访问过
        int[] visitedVertexArr = new int[graph.getVertexSize()];
        // 标记当前顶点为已访问
        visitedVertexArr[startVertexIndex] = 1;

        // 定义边的左右2个顶点下标, 最小权值
        int edgeLeftVertexIndex = 0, edgeRightVertexIndex = 0, minWeight = 0;

        // 因为graph有vertexSize个顶点，普利姆算法结束后，有vertexSize-1条边
        for (int x = 1; x < graph.getVertexSize(); x++) {
            // 循环遍历处理二维数组, 获取当前顶点对应的权值最小的顶点
            for (int j = 0; j < graph.getVertexSize(); j++) {
                for (int k = 0; k < graph.getVertexSize(); k++) {
                    if (visitedVertexArr[j] == 1 && visitedVertexArr[k] == 0 && (minWeight == 0 || weightArr[j][k] < minWeight)) {
                        // 顶点j被访问过, 顶点k未被访问过, 且权值小于最小权值, 则更新最小权值
                        minWeight = weightArr[j][k];
                        edgeLeftVertexIndex = j;
                        edgeRightVertexIndex = k;
                    }
                }
            }

            System.out.println("边<" + graph.getVertexArr()[edgeLeftVertexIndex] + ", " + graph.getVertexArr()[edgeRightVertexIndex] + "> 权值:" + minWeight);
            //将当前这个结点标记为已经访问
            visitedVertexArr[edgeRightVertexIndex] = 1;
            // 重置minWeight
            minWeight = 0;
        }
    }

    // 显示图的邻接矩阵
    public static void showGraph(PrimVillageGraph graph) {
        for (int[] linkWeight : graph.getWeightArr()) {
            System.out.println(Arrays.toString(linkWeight));
        }
    }

}
